Năm 1975, Võ Trọng Việt nhập ngũ và trở thành lính của tiểu đoàn 22, Quân khu 4.

Ngày 17 tháng 9 năm 1977, Võ Trọng Việt gia nhập Đảng Cộng sản Việt Nam.

Năm 1980, ông tốt nghiệp Trường Sĩ quan công an vũ trang (nay là Học viện Biên phòng) được phong quân hàm Thiếu uý và được phân công về phòng Trinh sát Quân khu V nhận nhiệm vụ đi biệt phái chống FULRO ở Đắk Lắk.

Năm 2000, ông đảm nhận cương vị chỉ huy trưởng Biên phòng Hà Tĩnh. Dấu ấn không thể không nhắc đến của ông lúc này là bảo tồn và phát triển người Chứt - một trong năm dân tộc ít người nhất của Việt Nam, được phát hiện trong rừng sâu. Từ chỗ chỉ còn vài chục người nay đã lên hơn 500 người.

Năm 2005, ông được điều động ra Bộ Tư lệnh Bộ đội Biên phòng Việt Nam làm Chính ủy, thăng hàm thiếu tướng. Cũng năm này, ông được phong Anh hùng Lực lượng vũ trang nhân dân. 

Tháng 5 năm 2007, ông trúng cử đại biểu Quốc hội khóa XII tại tỉnh Sơn La.[2]

Tháng 1 năm 2011, ông được bầu là Ủy viên Ban Chấp hành Trung ương Đảng Cộng sản Việt Nam khóa XI.

Ngày 22 tháng 5 năm 2011, ông trúng cử Đại biểu Quốc hội khóa XIII tại tỉnh Kon Tum.

Năm 2012, bổ nhiệm giữ chức Tư lệnh Bộ đội Biên phòng

Tháng 10 năm 2015, bổ nhiệm giữ chức Thứ trưởng Bộ Quốc phòng[3]

Tháng 01 năm 2016, ông tiếp tục tái cử Ủy viên Ban Chấp hành Trung ương Đảng Cộng sản Việt Nam khóa XII.

Ngày 4 tháng 4 năm 2016 được bầu làm Ủy viên Ban Thường vụ Quốc hội.

Ngày 5 tháng 4 năm 2016, ông giữ chức vụ Chủ nhiệm Ủy ban Quốc phòng và An ninh của Quốc hội.